package NO3_LinkedList;

/**
 * 2025-09-10
 * 力扣 - 92. 反转链表 II
 * <p>
 * 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。
 * 请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
 */
public class ReverseBetweenMain {
    public static void main(String[] args) {
        ListNode head = new ListNode(1,
                new ListNode(2,
                        new ListNode(3,
                                new ListNode(4,
                                        new ListNode(5)))));
        ListNode.printList(head);
        ListNode.printList(reverseBetween(head, 2, 4));
    }

    public static ListNode reverseBetween(ListNode head, int left, int right) {
        // 创建一个虚拟头节点，简化边界处理（特别是当left=1时）
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        // 步骤1：找到pre（即第left-1个节点）
        ListNode pre = dummy;
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }

        // 步骤2：找到rightNode（即第right个节点）
        ListNode rightNode = pre;
        for (int i = 0; i < right - left + 1; i++) {
            rightNode = rightNode.next;
        }

        // 步骤3：切断子链表
        ListNode leftNode = pre.next;  // 子链表的头
        ListNode succ = rightNode.next; // 子链表的后一个节点

        // 切断连接
        pre.next = null;
        rightNode.next = null;

        // 步骤4：反转子链表
        reverseLinkedList(leftNode);

        // 步骤5：重新连接
        pre.next = rightNode; // 反转后，rightNode变为子链表的头
        leftNode.next = succ; // 反转后，leftNode变为子链表的尾

        return dummy.next;
    }

    private static void reverseLinkedList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
    }
}
